#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

class Main {
	int MOD = 376544743;
	int n = 0, m = 0, k = 0, ss = 0, es = 0;
        int dp[8 + 1][1 << (8 << 1)];

	int set(int s, int j, int v)
	{
		return (s & ~(3 << (j << 1))) | (v << (j << 1));
	}

	int get(int s, int j)
	{
		return (s >> (j << 1)) & 3;
	}

	bool diffrent(int a, int b)
	{
		for (int i = 0; i < m; i++) {
			if (get(a, i) == get(b, i)) {
				return false;
			}
		}
		return true;
	}

	int specil()
	{
		if (n % 2) {
			for (int i = 0; i < m; i++) {
				if (get(es, i) != get(ss, i)) {
					return 0;
				}
			}
			return 1;
		} else {
			for (int i = 0; i < m; i++) {
				if (get(es, i) == get(ss, i)) {
					return 0;
				}
			}
			return 1;
		}
		return 0;
	}

	int cal_dp()
	{
                int maxs = 1 << (m << 1);
                memset(dp, 0, sizeof(dp));
		for (int s = 0; s < maxs; s++) {
			dp[m][s] = diffrent(s, es) ? 1 : 0;
		}

                int ans;
		for (int i = n - 2; i >= 1; i--) {
			for (int j = m - 1; j >= 0; j--) {
				for (int s = 0; s < maxs; s++) {
                                        ans = 0;
					for (int v = 0; v < k; v++) {
						if ((j == 0 || get(s, j - 1) != v) && get(s, j) != v) {
							ans = (ans + dp[j + 1][set(s, j, v)]) % MOD;
						}
					}
                                        dp[j][s] = ans;
				}
			}
                        ans = dp[0][ss];
                        copy(&dp[0][0], &dp[0][0] + maxs, &dp[m][0]);
		}
                return ans;
	}

    public:
	Main()
	{
		cin >> n >> m >> k;
		for (int i = 0, v = 0; i < m; i++) {
			cin >> v;
			ss = set(ss, i, v);
		}
		for (int i = 0, v = 0; i < m; i++) {
			cin >> v;
			es = set(es, i, v);
		}
	}
	int run()
	{
		if (k == 2) {
			return specil();
		}
                return cal_dp();
	}
};

int main()
{
	Main app;
	cout << app.run() << endl;
	return 0;
}